
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    //剑指 Offer 18. 删除链表的节点
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode* del = new ListNode(0);
        ListNode* guard = del;
        guard->next = head;
        ListNode* cur = head;
        while (cur && cur->val!=val)
        {
            guard = guard->next;
            cur = cur->next;
        }
        if (cur == nullptr)
        {
            delete del;
            return head;
        }
        guard->next = cur->next;
        guard = del->next;
        delete del;
        return guard;
    }

    //剑指 Offer 22. 链表中倒数第k个节点
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* fast = head;
        ListNode* last = head;
        while (fast && k--)
        {
            fast = fast->next;
        }
        while (fast)
        {
            last = last->next;
            fast = fast->next;
        }
        return last;
    }

    //剑指 Offer 25. 合并两个排序的链表
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* del = new ListNode(0);
        ListNode* guard = del;
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;

        while (cur1 && cur2)
        {
            if (cur1->val < cur2->val)
            {
                guard->next = cur1;
                cur1 = cur1->next;
            }
            else 
            {
                guard->next = cur2;
                cur2 = cur2->next;
            }
            guard = guard->next;
        }
        if (cur1)
        {
            guard->next = cur1;
        }
        else 
        {
            guard->next = cur2;
        }

        guard = del->next;
        delete del;
        return guard;
    }
};